import java.util.HashMap;
import java.util.Map;

/**
 * 1054.距离相等的条形码
 */
public class Exerciser8 {
    public int[] rearrangeBarcodes(int[] barcodes) {
        // 统计每一个数字出现的次数，根据次数进行插入
        // 每次处理相同的数据，每次放入都是隔一个放一个
        // 需要先处理出现次数最多的，之后的数据的处理顺序就无所谓了
        Map<Integer,Integer> hash = new HashMap<>(); // <数据，出现的次数>
        // 因为要先处理出现次数最多的数据，所以需要进行记录
        int maxValue = 0,maxCount = 0;
        for(int x : barcodes) {
            hash.put(x,hash.getOrDefault(x,0) + 1);
            if(maxCount < hash.get(x)) {
                maxValue = x;
                maxCount = hash.get(x);
            }
        }
        int n = barcodes.length;
        int[] ret = new int[n];
        // 处理最多的
        int index = 0;
        for(int i = 0;i < maxCount;i++) {
            ret[index] = maxValue;
            index += 2;
        }

        // 从哈希表中移除，maxValue，之后处理剩余的数据，顺序数无所谓的
        hash.remove(maxValue);
        for(int x : hash.keySet()) {
            for(int i = 0;i < hash.get(x);i++) {
                // index最多循环到头一次
                if(index >= n) {
                    index = 1;
                }
                ret[index] = x;
                index += 2;
            }
        }

        return ret;
    }
}
